
# Definition of ListNode
class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

    def show(self):
        self.show_v()

        if self.next:
            self.next.show()

    def show_v(self):
        print('v: %s' % self.val)


class Solution:
    """
    @param head: a ListNode
    @return: a ListNode

    输入 1 2 3 4, 输出 2 1 4 3, 两两交换
    """

    def _swapPairs(self, head):

        if head and head.next:
            next_first = head.next.next    # backup

            first, second = head.next, head
            first.next, second.next = second, next_first           # new link

            head = first                  # new head

            pre = second                  # new pre

        else:
            return head

        while next_first and next_first.next:
            first, second = next_first.next, next_first
            next_first = next_first.next.next   # backup

            pre.next = first
            first.next, second.next = second, next_first
            pre = second

        return head

    def swapPairs(self, head):
        dummy = ListNode(0, head)       # 作为哨兵
        pre = dummy                     # pre作为pre的同时, 也有哨兵的作用

        while pre.next and pre.next.next:
            n1, n2 = pre.next, pre.next.next
            pre.next, n2.next, n1.next  = n2, n1, n2.next
            pre = n1

        # while first and first.next:
        #     second = first.next

        #     pre.next = second
        #     new_first = second.next
        #     second.next = first
        #     first.next = new_first

        #     pre = first
        #     first = new_first

        return dummy.next


def build_link_list():
    l5 = ListNode(5, None)
    l4 = ListNode(4, l5)
    l3 = ListNode(3, l4)
    l2 = ListNode(2, l3)
    l1 = ListNode(1, l2)

    # l2 = ListNode(2, None)
    # l1 = ListNode(1, l2)

    # l1 = ListNode(1, None)

    return l1

s = Solution()
l = build_link_list()
l = s.swapPairs(l)
l.show()
